최단 경로 알고리즘의 종류

최단 경로 계산 방식

One-To-One

한 지점에서 다른 특정 지점까지의 최단 경로
다익스트라(Dijkstra) 알고리즘

One-To-All

한 지점에서 다른 모든 지점까지의 최단 경로
다익스트라(Dijkstra) 알고리즘
벨만-포드 알고리즘(Bellman-Ford Algorithm)

All-To-All

모든 지점에서 모든 지점까지의 최단 경로
플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)

주요 알고리즘

너비 우선 탐색(BFS) 알고리즘

가중치가 없거나, 모든 가중치가 같은 경우 가장 빠름

다익스트라(Dijkstra) 알고리즘

음의 가중치가 없는 그래프에서의 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제
그리디 + DP(Dynamic Programming)
-> 현재 위치한 노드에서 최선의 경로를 반복적으로 찾으며, 이전에 계산해 둔 경로를 활용하여 중복된 하위 문제를 풀기 때문

벨만-포드 알고리즘(Bellman-Ford Algorithm)

가중 그래프에서의 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제

플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)

전체 All-To-All 문제